1. Technical Field of the Invention
The invention relates generally to communication systems; and, more particularly, it relates to calculations performed within decoders implemented within such communication systems.
2. Description of Related Art
Data communication systems have been under continual development for many years. One such type of communication system that has been of significant interest lately is a communication system that employs turbo codes. Another type of communication system that has also received interest is a communication system that employs Low Density Parity Check (LDPC) code. LDPC codes are oftentimes referred to in a variety of ways. For example, iterative soft decoding of LDPC codes may be implemented in a number of ways including based on the Belief Propagation (BP) algorithm, the Sum-Product (SP) algorithm, and/or the Message-Passing (MP) algorithm; the MP algorithm is sometimes referred to as a Sum Product/Belief Propagation combined algorithm. While there has been a significant amount of interest and effort directed towards these types of LDPC codes, regardless of which particular manner of iterative decoding algorithm is being employed in the specific case (3 of which are enumerated above: BP, SP, and MP), there still is ample room for improvement in the implementation and processing to be performed within a device to complete such decoding. For example, there are a variety of relatively complex and numerically burdensome calculations, data management and processing that must be performed to effectuate the accurate decoding of an LDPC coded signal.
A primary directive in these areas of development has been to try continually to lower the error floor within a communication system. The ideal goal has been to try to reach Shannon's limit in a communication channel. Shannon's limit may be viewed as being the data rate that is used in a communication channel, having a particular signal to noise ratio (SNR), that will achieve error free transmission through the channel. In other words, the Shannon limit is the theoretical bound for channel capacity for a given modulation and code rate.
LDPC code has been shown to provide for excellent decoding performance that can approach the Shannon limit in some cases. For example, some LDPC decoders have been shown to come within 0.3 dB from the theoretical Shannon limit. While this example was achieved using an irregular LDPC code of a length of one million, it nevertheless demonstrates the very promising application of LDPC codes within communication systems.
In performing calculations when decoding a received signal, it is common for decoders to operate in the natural log (ln) domain; LDPC decoders also fall in to this category. By operating within the natural log domain, this converts all multiplications to additions, divisions to subtractions, and eliminates exponentials entirely, without affecting BER performance.
One somewhat difficult calculation is the natural log (ln) domain includes calculating the sum of exponentials as shown below:ln(ea+eb+ec+ . . . )
This calculation can be significantly reduced in complexity using the Jacobian formula shown below:max*(a,b)=ln(ea+eb)=max(a,b)+ln(1+e−|a−b|)
This calculation is oftentimes referred to as being a max* calculation or max* operation. It is noted that the Jacobian formula simplification of the equation shown above presents the max* operation of only two variables, a and b. This calculation may be repeated over and over when trying to calculate a longer sum of exponentials. For example, to calculate ln(ea+eb+ec), the following two max* operations may be performed:max*(a,b)==ln(ea+eb)=max(a,b)+ln(1+e−|a−b|)=xmax*(a,b,c)=max*(x,c)=ln(ex+ec)=max(x,c)+ln(1+e−|x−c|)
While there has a been a great deal of development within the context of LDPC code, the extensive processing and computations required to perform decoding therein can be extremely burdensome—this one example above of the calculating the sum of exponentials illustrates the potentially complex and burdensome calculations needed when performing decoding. Sometimes the processing requirements are so burdensome that they simply prohibit their implementation within systems having very tight design budgets.
There have been some non-optimal approaches to deal with the burdensome calculations required to do such burdensome calculations. For example, in performing this basic max* operation, some decoders simply exclude the logarithmic correction factor of ln(1+e−|a−b|) altogether and use only the max(a,b) result which may be implemented within a single instruction within a digital signal processor (DSP). However, this will inherently introduce some degradation in decoder performance. Most of the common approaches that seek to provide some computational improvements either cut corners in terms of computational accuracy, or they do not provide a sufficient reduction in computational complexity to justify their integration. One of the prohibiting factors concerning the implementation of many LDPC codes is oftentimes the inherent computational complexity coupled with the significant amount of memory required therein.
Other types of comparably complex calculations that may sometimes be employed when decoding coded signals includes the min** (min-double-star) operation and the max** (max-double-star) operation. The prior art means by which min** processing and max** processing are performed are less than ideal and would benefit greatly from some more efficient designs and implementations.
Many of these calculations performed when decoding such coded signals are relatively complex. Because of this, many prior art approaches to design hardware to perform these complex calculations are also very complex. Moreover, many designers implement non-exact hardware solutions to make these calculations (e.g., approximations of the actual calculations needed to decode such signals).
FIG. 6A is a diagram illustrating a prior art embodiment of min** (min-double-star) processing 601. This diagram shows one possible prior art approach by which min** processing may be implemented. This functional block operates on two input values, shown as A and B. The difference between the two values, A−B, and the sum of the two values, A+B, are both calculated. The two values, A and B, are also provided to a MUX (Multiplexor) 610, whose selection signal determines the output as being A or B based on the sign bit of the difference between the two values, A−B. For example, only one of A or B is output from the MUX 610. If A is less than B, then the sign bit of the difference between the two values, A−B, is 0, and if A is greater than B, hen the sign bit of the difference between the two values, A−B, is 1.
Therefore, the MUX 610 is implemented such that when A is greater than B, then the sign bit of the difference between the two values, A−B, selects B as being output from the MUX 610. In other words, B is then the minimum of two input values, i.e. min(A,B)=B. Analogously, the MUX 610 is also implemented such that when A is less than B, then the sign bit of the difference between the two values, A−B, selects A as being output from the MUX 610. In other words, A is then the minimum of two input values, i.e. min(A,B)=A.
Also, the difference between the two values, A−B, and the sum of the two values, A+B, are each provided to a first log correction functional block 620 and a second log correction functional block 630, respectively. The difference between the two values, A−B, is used by the first log correction functional block 620 to determine a first log correction factor, −ln(1+e−|A−B|). This first log correction factor includes an absolute value function of the difference between the two values, A−B. Analogously, the sum of the two values, A+B, is used by the second log correction functional block 630 to determine a second log correction factor, ln(1+e−(A+B)). This second log correction factor does not include an absolute value function of the sum of the two values, A+B.
The min** processing resultant is composed of the sum of the first log correction factor, −ln(1+e−|A−B|), the second log correction factor, ln(1+e−(A+B)), and the minimum of two input values, i.e. min(A,B)=A or B. Mathematically, this may be shown as follows:min**(A,B)=min(A,B)−ln(1+e−|A−B|)+ln(1+e−(A+B))
FIG. 6B is a diagram illustrating a table of possible log correction factors 602 that may be employed using the prior art embodiment of min** processing of FIG. 6A. Sometimes, various means may be employed to pre-calculate (e.g., to predetermine) a range of possible values for these log correction factors. This table shows a range of possible values for the second log correction factor, ln(1+e−(A+B)), as a function of sum of the two values, A+B. As can clearly be seen, the possible values of the second log correction factor, ln(1+e−(A+B)), continue to increase as the sum of the two values, A+B, continues to decrease. To store a large number of possible values of the second log correction factor, ln(1+e−(A+B)), for a wide variety of different possible values of the sum of the two values, A+B, would inherently require a relatively large amount of memory. The larger the memory device being employed to store a relatively broad range of possible values of the second log correction factor, ln(1+e−(A+B)), then a larger surface area will be consumed within an actual device that is implemented to perform such calculations and the greater the cost of such an actual device.
There still exists a need in the art to provide for more efficient solutions when making calculations, such as min** (min-double-star) and max** (max-double-star), within decoders that operate within the logarithmic domain.
The use of LDPC coded signals continues to be explored within many newer application areas. One such application area is that digital video broadcasting. The Digital Video Broadcasting Project (DVB) is an industry-led consortium of over 260 broadcasters, manufacturers, network operators, software developers, regulatory bodies and others in over 35 countries committed to designing global standards for the global delivery of digital television and data services. Publicly available information concerning the DVB is available at the publicly available Internet site of the DVB.
The DVB-S2 (i.e., DVB-Satellite Version 2) draft standard is also publicly available at the Internet site of the DVB.
Greater detail regarding the types of signals employed within such DVB-S2 compliant systems is included within this DVB-S2 standard. The DVB-S2 standard focuses primarily on the transmission system description and the subsystems therein including mode adaptation, stream adaptation, FEC encoding (including both BCH outer encoding and LDPC inner encoding), bit mapping into constellation, physical layer framing, and baseband shaping and quadrature modulation.
The DVB-S2 is an advanced version of DVB-S (the first standard produced by the Digital Video Broadcasting Project). DVB-S2 seeks to provide for greater efficiency than DVB-S. DVB-S2 plans to implement 4 different modulation types: QPSK (Quadrature Phase Shift Key), 8 PSK (Phase Shift Key), 16 APSK (Asymmetric Phase Shift Keying), and 32 APSK. Generally speaking, the QPSK and 8 PSK modulation types are intended for broadcast applications through non-linear satellite transponders driven near to saturation; the 16 APSK and 32 APSK modulation types are geared more primarily towards professional applications requiring semi-linear transponders. The 16 APSK and 32 APSK modulation types operate by trading off power efficiency for greater throughput.
In addition, DVB-S2 uses a powerful FEC (Forward Error Correction) system based on concatenation of BCH (Bose-Chaudhuri-Hocquenghem) outer coding with LDPC inner coding. The result is performance which is at times only 0.7 dB from the Shannon limit. The choice of FEC parameters depends on the system requirements. With VCM (Variable Coding and Modulation) and ACM (Adaptive Coding and Modulation), the code rates can be changed dynamically, on a frame by frame basis.
The multiple operational parameters to which a receiving device, that includes a decoder, must operate to be DVB-S2 compliant is very clearly laid out by the operational parameters of the transmission system description. However, as long as a receiving device, that includes a decoder, complies with these operational parameters specified within the DVB-S2 standard, great latitude in the means of implementation is permissible. The generation of signals on the transmission end of a communication channel is clearly laid out within the DVB-S2 standard, and the means by which the receive processing of such signal (at the receiving end of a communication channel) may be performed is widely open to the designer. Clearly, a key design constrain of such receiving devices is to provide for the accommodation of such DVB-S2 signals while providing for very high performance while occupying a relatively small amount of area and having a relatively lower level of complexity.
Another application area in which the use of LDPC coded signals continues to be explored is in various communication system embodiments and application areas whose operation is specified and governed by the IEEE (Institute of Electrical & Electronics Engineers). For example, the use of LDPC coded signals has been of significant concern within the IEEE P802.3an (10 GBASE-T) Task Force. This IEEE P802.3an (10 GBASE-T) Task Force has been created by the IEEE to develop and standardize a copper 10 Giga-bit Ethernet standard that operates over twisted pair cabling according the IEEE 802.3 CSMA/CD Ethernet protocols. Carrier Sense Multiple Access/Collision Detect (CSMA/CD) is the protocol for carrier transmission access in Ethernet networks. IEEE 802.3an (10 GBASE-T) is an emerging standard for 10 Gbps Ethernet operation over 4 wire twisted pair cables. More public information is available concerning the IEEE P802.3an (10 GBASE-T) Task Force at the publicly available Internet sites of the working groups of the IEEE.
This high data rate provided in such applications is relatively close to the theoretical maximum rate possible over the worst case 100 meter cable. Near-capacity achieving error correction codes are required to enable 10 Gbps operation. The latency constraints, which would be involved by using traditional concatenated codes, simply preclude their use in such applications.
Typical encoding and modulation of LDPC coded signals is performed by generating a signal that includes symbols each having a common code rate and being mapped to a singular modulation (e.g., a singular constellation shape having a singular mapping of the constellation points included therein). That is to say, all of the symbols of such an LDPC coded modulation signal have the same code rate and the same modulation (the same constellation shape whose constellation points have the singular mapping). Oftentimes, such prior art designs are implemented as to maximize the hardware and processing efficiencies of the particular design employed to generate the LDPC coded signal having the single code rate and single modulation for all of the symbols generated therein.
However, in some more recent prior art LDPC communication systems, the design of LDPC encoders has sought to provide for capabilities to generate multiple types of LDPC coded signals. Within these communication systems, the code rate and modulation type for all of the symbols within any given LDPC block is the same. That is to say, the entire block has a particular code rate and modulation type associated with it. Nevertheless, the encoder is operable to generate different LDPC blocks such that a first LDPC block has a first code rate and first modulation type associated with it, and a second LDPC block has a second code rate and second modulation type associated with it.
A decoder that operates to decode such signals must be able to accommodate the various LDPC block types that it may receive. Currently, the LDPC decoder designs being discussed in the art require a relatively large amount of area and are of a relatively high complexity. There is a need in the art to provide for an LDPC decoder that can accommodate such signals while providing for very high performance, less area, and less complexity.
Generally speaking, there is a seemingly continual in the art to provide for means by which the calculations and processing to be performed within decoders that are operable to decode coded signals. This is true with respect to virtually any type of coded signals, including turbo coded signals, TTCM (Turbo Trellis Coded Modulation) signals, LDPC coded signals, and other types of coded signals. Improvements in the hardware and functional blocks employed to perform the various calculations required therein could benefit the efficiency of the decoding processing implemented within many decoders.